Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,

Given [3,2,1,5,6,4] and k = 2, return 5.

Note:

You may assume k is always valid, 1 ≤ k ≤ array’s length.

Solution:

  1. public class Solution {
  2.   public int findKthLargest(int[] a, int k) {
  3.     int n = a.length;
  4.     int p = quickSelect(a, 0, n - 1, n - k + 1);
  5.     return a[p];
  6.   }
  8.   // return the index of the kth smallest number
  9.   int quickSelect(int[] a, int lo, int hi, int k) {
  10.     // use quick sort's idea
  11.     // put nums that are <= pivot to the left
  12.     // put nums that are  > pivot to the right
  13.     int i = lo, j = hi, pivot = a[hi];
  14.     while (i < j) {
  15.       if (a[i++] > pivot) 
  16.         swap(a, --i, --j);
  17.     }
  18.     swap(a, i, hi);
  20.     // count the nums that are <= pivot from lo
  21.     int m = i - lo + 1;
  23.     // pivot is the one!
  24.     if (m == k)     return i;
  25.     // pivot is too big, so it must be on the left
  26.     else if (m > k) return quickSelect(a, lo, i - 1, k);
  27.     // pivot is too small, so it must be on the right
  28.     else            return quickSelect(a, i + 1, hi, k - m);
  29.   }
  31.   void swap(int[] a, int i, int j) {
  32.     int tmp = a[i];
  33.     a[i] = a[j];
  34.     a[j] = tmp;
  35.   }
  36. }